package dfs_and_bfs


type tFIFOQueue struct {
	nodes []INode
	capacity int
	rindex int
	windex int
}

func newFIFOQueue() iNodeQueue {
	it := &tFIFOQueue{}
	it.Clear()
	return it
}

func (me *tFIFOQueue) Clear() {
	me.nodes = make([]INode, 0)
	me.capacity = 0
	me.rindex = -1
	me.windex = -1
}

func (me *tFIFOQueue) size() int {
	return me.windex - me.rindex
}

func (me *tFIFOQueue) Empty() bool {
	return me.size() <= 0
}

func (me *tFIFOQueue) Push(node INode) {
	me.ensureSpace(1)
	me.windex++
	me.nodes[me.windex] = node
}

func (me *tFIFOQueue) ensureSpace(size int) {
	for me.capacity < me.windex + size + 1 {
		me.nodes = append(me.nodes, nil)
		me.capacity++
	}
}

func (me *tFIFOQueue) Poll() (bool, INode) {
	if me.Empty() {
		return false, nil
	}

	me.rindex++
	it := me.nodes[me.rindex]
	me.nodes[me.rindex] = nil

	if me.rindex > me.capacity / 2 {
		size := me.size()
		offset := me.rindex + 1
		for i := 0;i < size;i++ {
			me.nodes[i], me.nodes[i + offset] = me.nodes[i + offset], nil
		}

		me.rindex -= offset
		me.windex -= offset
	}

	return true, it
}